﻿#pragma once
#include "Index.h"

class IMaxestSumOfSubArr
{
public:
	/**
	 *  连续子数组最大和.
	 *	https://www.nowcoder.com/practice/1718131e719746e9a56fb29c40cc8f95?tpId=230&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D230
	 *
	 * 描述
	 * 给定一个长度为n的数组，数组中的数为整数。
	 * 请你选择一个非空连续子数组，使该子数组所有数之和尽可能大，子数组最小长度为1。求这个最大值。
	 *
	 * 输入描述：
	 * 第一行为一个正整数 n ，代表数组的长度。1≤n≤2∗10^5
	 * 第二行为n个整数a[i]，用空格隔开，代表数组中的每一个数。 |a[i]|<10^2
	 * 输出描述：
	 * 连续子数组的最大之和。
	 */
	virtual int maxSumOfSubArr(std::vector<int>& arr) = 0;
};
class MaxestSumOfSubArr
{
public:
	class DP:public IMaxestSumOfSubArr
	{
	public:
		int maxSumOfSubArr(std::vector<int>& arr) override
		{

			if (arr.empty())
				return 0;
			const int arrSize = arr.size();
			//遍历arr走到i位置时，dp表示以 i-1 位置结尾的子数组的最大值和
			int dp = arr[0];
			//连续子数组的最大之和结果值
			int maxSum = dp;

			for (int i = 1; i < arrSize; ++i)
			{
				//arr[i]归入之前的连续子数组 或 不规入
				dp = std::max<>(dp + arr[i], arr[i]);
				maxSum = std::max<>(dp, maxSum);
			}
			return maxSum;
		}
	};
};


#ifdef DEV_TEST
#include <gtest/gtest.h>
class MaxestSumOfSubArrTest:public SolutionTestor<IMaxestSumOfSubArr>
{
protected:
	void LoadSolutions(std::vector<IMaxestSumOfSubArr*>& solutions) override
	{
		solutions = {
			new MaxestSumOfSubArr::DP,
		};
	}
};
TEST_F(MaxestSumOfSubArrTest, maxSumOfSubArr)
{
	TestForSolutions([](IMaxestSumOfSubArr* solution)
		{
			const int arrSize = std::rand() % 200000;
			std::vector<int> arr=TestingUtil::randRangeInts(arrSize, -100, 100);

			int expectMaxSum = 0;
			for(int i=0;i<arrSize;++i)
				for(int j=i;j<arrSize;++j)
				{
					int sum = 0;
					for(int k=i;k<=j;++k)
						sum += arr[k];
					expectMaxSum = std::max<>(sum, expectMaxSum);
				}

			const auto result= solution->maxSumOfSubArr(arr);
			EXPECT_EQ(result, expectMaxSum);
		});
}
#endif